Palindrome Permutation II

Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.

For example:

Given s = "aabb", return ["abba", "baab"].

Given s = "abc", return [].

Hint:

  1. If a palindromic permutation exists, we just need to generate the first half of the string.
  2. To generate all distinct permutations of a (half of) string, use a similar approach from: Permutations II or Next Permutation.

Solution:

  1. public class Solution {
  2.   public List<String> generatePalindromes(String s) {
  3.     int odd = 0;
  4.     String mid = "";
  5.     List<String> res = new ArrayList<>();
  6.     List<Character> list = new ArrayList<>();
  7.     Map<Character, Integer> map = new HashMap<>();
  9.     // step 1. build character count map and count odds
  10.     for (int i = 0; i < s.length(); i++) {
  11.       char c = s.charAt(i);
  12.       map.put(c, map.containsKey(c) ? map.get(c) + 1 : 1);
  13.       odd += map.get(c) % 2 != 0 ? 1 : -1;
  14.     }
  16.     // cannot form any palindromic string
  17.     if (odd > 1) return res;
  19.     // step 2. add half count of each character to list
  20.     for (Map.Entry<Character, Integer> entry : map.entrySet()) {
  21.       char key = entry.getKey();
  22.       int val = entry.getValue();
  24.       if (val % 2 != 0) {
  25.         mid += key;
  26.       }
  28.       for (int i = 0; i < val / 2; i++) list.add(key);
  29.     }
  31.     // step 3. generate all the permutations O(n!/2)
  32.     getPerm(list, mid, new boolean[list.size()], new StringBuilder(), res);
  34.     return res;
  35.   }
  37.   // generate all unique permutation from list
  38.   void getPerm(List<Character> list, String mid, boolean[] used, StringBuilder sb, List<String> res) {
  39.     if (sb.length() == list.size()) {
  40.       // form the palindromic string
  41.       res.add(sb.toString() + mid + sb.reverse().toString());
  42.       sb.reverse();
  43.       return;
  44.     }
  46.     for (int i = 0; i < list.size(); i++) {
  47.       // avoid duplication
  48.       if (i > 0 && list.get(i) == list.get(i - 1) && !used[i - 1]) {
  49.         continue;
  50.       }
  52.       if (!used[i]) {
  53.         used[i] = true;
  54.         sb.append(list.get(i));
  56.         getPerm(list, mid, used, sb, res);
  58.         sb.deleteCharAt(sb.length() - 1);
  59.         used[i] = false;
  60.       }
  61.     }
  62.   }
  63. }